The present invention relates to the optimisation of sequential combinatorial processes.
There are numerous examples of processes that comprise the performance of a to series of steps, the end result of which can be optimised by carrying out the steps in a preferred manner. Manufacturing processes, for example, may include steps in which the size, quantity, duration, pressure, temperature, viscosity, etc, of particular variables affects the quality of the manufactured product. Industry is naturally concerned with achieving quality, so it is frequently desirable to optimise the various steps to obtain the best possible end result.
This optimisation is often done by modelling of the process. In this way, different values of a parameter or group of parameters can be compared to determine which gives the best result. One modelling technique that is of particular interest due its high accuracy and ability to cope with complex scenarios is finite element (FE) analysis. For the type of process in question, the model generally considers the parameters of interest as being defined in a continuous numerical space in which the parameters may take any value, and seeks the optimum value of each having regard to the others. However, in terms of computational time required, this is an expensive approach. A single “run” of an FE model for one set of values of the parameters may take many hours, and typically there are many different values to be considered. This means that the model may take many thousands of iterations to converge to any optimum solution, so that a full study of the process may take an unfeasibly long time. The cost of this may outweigh any benefit achieved from optimising the process.
This disadvantage has been addressed by so-called surrogate modelling. The idea of using surrogate models in optimisation has been widely explored for problems related to expensive computations. The surrogate is a simple approximation of the FE (or other complex) model, with a shorter iteration time so that it is faster to compute. A well-known surrogate model is kriging, but any other approximation method suitable to the specific problem can be used. Results from a few runs of the finite element analysis model are supplied to the surrogate model, to “train” it. The quantity of these runs depends on the complexity of the process under study; usually 20-30 runs are enough to give a sufficient level of accuracy. Once the surrogate is trained, it is put through an optimisation cycle, in which it calculates the result of the process for all possible values of the parameter or parameters of interest, and returns the value corresponding to the optimal result of the process. However, this optimal value is based on the approximation of the surrogate model and may be inaccurate. Therefore, it is common to run the FE model for the same values of the parameters, and compare the result with that from the surrogate. If there is a significant difference, the result of this latest FE run is then fed to the surrogate to improve its training, and the surrogate is again put through an optimisation cycle, and so on until acceptable agreement between the two models is reached. In this way, the surrogate model becomes more accurate in the region of the optimum, because accuracy is only added where and when it is needed. The overall computational time needed to obtain the optimal value is reduced by transferring the bulk of the computational load from the slow FE model to the faster surrogate. For example, a single FE run can take about 48 hours, while 50000 surrogate evaluations can be performed in less than ten minutes.
Further, the accuracy can be enhanced by careful selection of the initial FE model runs to include a range of parameter values that covers those thought likely to be of importance in determining the optimal value. This is known as Design of Experiments (DoE), and a voids potential waste of computational time in modelling scenarios that lie far from the desired result. An example of a modelling process that uses finite element analysis together with DoE can be found in U.S. Pat. No. 6,349,467 [1], where the technique is applied to optimising the steps in a process for manufacturing deflector plates for gas turbine engine combustors so as to avoid undesirable intermediate heat treatment of sheet metal used to form the deflector plates.
To date, surrogate-supplemented FE modelling has been applied to a wide range of problems in which it is desired to optimise the numerical value of one or more parameters used in a process. The problems have been limited to those which can be approximated by a surrogate model function that depends on variables that have a continuous or discrete nature and can be physically or quantitatively expressed. However, there is a further set of processes which can benefit from optimisation, but to which the known surrogate modelling techniques cannot be applied, because the problem does not lie in finding an optimum numerical value of a parameter. These processes are those that comprise several steps, or events, that can be performed, or combined, in any order, or sequence, to achieve the end result of the process. However, the quality of the end result depends on the order in which the steps are performed. In other words, there are no surrogate model optimisation techniques available in the combinatorial domain, in which variables have no physical meaning. The goal is to determine the optimum ordering of the events, so as to get the best result. Hence, this problem can be referred to as a sequential combinatorial optimisation problem; in what sequence should the events be combined to give the optimum result? It will be appreciated that this is a problem distinct from that of determining the optimum value of a quantifiable parameter; individual events and their ordering are non-numerical items without physical meaning. Thus far, it has been largely necessary to rely on full FE analysis studies to solve these kinds of optimisation problems.
Great benefit would be conferred by a method offering an improved optimisation technique for sequential combinatorial processes.